﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;



	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53,
				97,
				193,
				389,
				769,
				1543,
				3079,
				6151,
				12289,
				24593,
				49157,
				98317,
				196613,
				393241,
				786433,
				1572869,
				3145739,
				6291469,
				12582917, 25165843,
				50331653,
				100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	template <class K, class V, class Ptr, class Ref, class KeyOfValue, class HF>
	struct HBIterator;
	// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	template<class K, class V, class KeyOfValue, class HashFunc>
	class HashBucket
	{

		template <class K, class V, class Ptr, class Ref, class KeyOfValue, class HF>
		friend struct HBIterator;
	public:
		typedef HashFunc Hash;
		typedef HBIterator<K, V, V*,V&, KeyOfValue, Hash> Iterator;
		typedef HBIterator<K, V, const V*,const V&, KeyOfValue, Hash> Const_Iterator;

		
		//typedef HBIterator<K, const V, KeyOfValue, Hash> Const_Iterator;

		typedef HashNode<V> Node;
	public:
		HashBucket(int _size = 10)
		{
			_tables.resize(_size, nullptr);
			for (auto& e : _tables) {
				e = new Node(V());
			}
		}

		// 哈希桶的销毁
		~HashBucket()
		{
			// 依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
				//if (i + 1 == _tables.size()) cout << "ljjdsd" << endl;
			}
		}

		Const_Iterator begin() const {
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			Node* _pNode = _tables[0];
			if (_pNode->_next)
				_pNode = _pNode->_next;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				int hash1 = 0;
				hash1++;
				while (hash1 < _tables.size()) {
					if (_tables[hash1]->_next) {
						break;
					}
					else {
						hash1++;
					}
				}
				if (hash1 == _tables.size()) {
					_pNode = nullptr;
				}
				else {
					_pNode = _tables[hash1]->_next;
				}

			}
			return Const_Iterator(_pNode, this);
		}
	
		Iterator begin() {
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			Node* _pNode = _tables[0];
			if (_pNode-> _next)
				_pNode = _pNode-> _next;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				int hash1 = 0;
				hash1++;
				while (hash1 < _tables.size()) {
					if (_tables[hash1]->_next) {
						break;
					}
					else {
						hash1++;
					}
				}
				if (hash1 == _tables.size()) {
					_pNode = nullptr;
				}
				else {
					_pNode = _tables[hash1]->_next;
				}

			}
			return Iterator(_pNode, this);
		}
		
		Iterator end() {
			
			return Iterator(nullptr, this);
		}
		Const_Iterator end() const {
			return Const_Iterator(nullptr, this);
		}

		size_t size() const{ return _n; }
		bool empty()const {
			if (_n == 0) return true;
			else return false;
		}

		size_t Count(const K& key) {
			if (find(key)) return 1;
			return 0;
		}
		// 插入值为data的元素，如果data存在则不插入
		pair<Iterator, bool> Insert(const V& data) {
			
			int N = _n;
			int M = _tables.size();
			int fac = N * 10 / M;
			KeyOfValue keyof;
			Iterator it = Find(keyof(data));
			if (it != end()) {
				return make_pair(it, false);
			}
			if (fac >= 7) {
				//扩容
				vector<Node*> tem;
				tem.swap(_tables);
				_tables.resize(__stl_next_prime(M + 1));
				M = _tables.size();

				for (int i = 0; i < M; i++) {
						_tables[i] = new Node(V());
				}

				for (auto e : tem) {
					e = e->_next;
					while (e) {
						Hash hash;
						Node* enext = e->_next;
						int hash1 = hash(keyof(e->_data)) % M;
						e->_next = _tables[hash1]->_next;
						_tables[hash1]->_next = e;
						e = enext;
					}
				}
			}
			Hash hash;
			int hash1 = hash(keyof(data)) % M;
			Node* newhashnode = new Node(data);
			newhashnode->_next = _tables[hash1]->_next;
			_tables[hash1]->_next = newhashnode;
			++_n;
			return make_pair(Iterator(newhashnode),true);
		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
		Iterator Find(const K& key) {
			Hash hash;
			int M = _tables.size();
			int hash1 = hash(key) % M;
			Node* cur = _tables[hash1]->_next;
			KeyOfValue keyof;
			while (cur) {
				if (keyof(cur->_data) == key) return Iterator(cur,this);
				cur = cur->_next;
			}

			return end();
		}
		size_t BucketCount() { return _tables.size(); }
		size_t BucketSize(const K& key) {
			int M = _tables.size();
			int hashi = key % _tables.size();
			Node* cur = _tables[hashi];
			int num = 0;
			while (cur->_next)
			{
				num++;
				cur = cur->_next;
			}
			return num;
		}
		// 哈希桶中删除key的元素，删除成功返回true，否则返回false
		Iterator  Erase(Iterator it) {
			K key = KeyOfValue()(*it);
			Hash hash;
			int M = _tables.size();
			int hash1 = hash(key) % M;
			Node* cur = _tables[hash1]->_next;
			KeyOfValue keyof;
			Node* parent = _tables[hash1];
			while (cur) {
				if (keyof(cur->_data) == key) {
					parent->_next = cur->_next;
					delete cur;
					_n--;
					return Iterator(cur,this);
				}
				parent = cur;
				cur = cur->_next;
			}
			return end();
		}

	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};

// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
template <class K, class V, class Ptr,class Ref,class KeyOfValue, class HF>
struct HBIterator
{
	typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
	typedef HashNode<V>* PNode;
	typedef HBIterator<K, V, Ptr,Ref,KeyOfValue, HF> Self;
	typedef HBIterator<K, V, V*, V&, KeyOfValue, HF> iterator;

	HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr) :_pNode(pNode) ,_pHt(pHt){}

	HBIterator(const iterator& other) {
		_pHt = other._pHt; _pNode = other._pNode;
	}
	Self & operator++()
	{
		// 当前迭代器所指节点后还有节点时直接取其下一个节点
		if (_pNode-> _next)
			_pNode = _pNode-> _next;
		else
		{
			// 找下一个不空的桶，返回该桶中第一个节点
			KeyOfValue kot;
			int hash1 = HF()(kot(_pNode->_data)) % _pHt->_tables.size();
			hash1++;
			while (hash1 < _pHt->_tables.size()) {
				if (_pHt->_tables[hash1]->_next) {
					break;
				}
				else {
					hash1++;
				}
			}
			if (hash1 == _pHt->_tables.size()) {
				_pNode = nullptr;
				
			}
			else {
				_pNode = _pHt->_tables[hash1]->_next;
			}

		}

		return *this;
	}
	Self operator++(int) {
		// 当前迭代器所指节点后还有节点时直接取其下一个节点
		Self* _up = this;
		if (_pNode-> _next)
			_pNode = _pNode-> _next;
		else
		{
			// 找下一个不空的桶，返回该桶中第一个节点
			KeyOfValue kot;
			int hash1 = HF()(kot(_pNode->_data)) % _pHt->_tables.size();
			hash1++;
			while (hash1 < _pHt->_tables.size()) {
				if (_pHt->_tables[hash1]->_next) {
					break;
				}
				else {
					hash1++;
				}
			}
			if (hash1 == _pHt->_tables.size()) {
				_pNode = nullptr;
			}
			else {
				_pNode = _pHt->_tables[hash1]->_next;
			}

		}

		return *_up;
	}

	Ref operator*() {
		return _pNode->_data;
	}
	Ptr operator->() {
		return &_pNode->_data;
	}
	Self& operator=(Self& it) {
		_pNode = it._pNode;
		_pHt = it._pHt;
		return *this;
	}

	bool operator==(const Self& it) const {
		return _pNode == it._pNode;
	}
	bool operator!=(const Self& it) const {
		return _pNode != it._pNode;
	}
	PNode _pNode;             // 当前迭代器关联的节点
	HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
};

// unordered_set中存储的是K类型，HF哈希函数类型
// unordered_set在实现时，只需将hashbucket中的接口重新封装即可
template<class K>
struct DefHashF
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
//模板特例化
struct DefHashF<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

template<class K, class HF = DefHashF<K>>
class unordered_set
{
	// 通过key获取value的操作
	struct KeyOfValue
	{
		const K& operator()(const K& data)
		{
			return data;
		}
	};
	
	typedef HashBucket<K, const K, KeyOfValue, HF> HT;

public:
	typename typedef HT::Iterator iterator;
public:
	unordered_set() : _ht()
	{}
	////////////////////////////////////////////////////
	iterator begin() { return _ht.begin(); }
	iterator end() { return _ht.end(); }
	////////////////////////////////////////////////////////////
	// capacity
	size_t size()const { return _ht.size(); }
	bool empty()const { return _ht.empty(); }
	///////////////////////////////////////////////////////////
	// lookup
	iterator find(const K& key) { return _ht.Find(key); }
	size_t count(const K& key) { return _ht.Count(key); }
	/////////////////////////////////////////////////
	// modify
	pair<iterator, bool> insert(const K& valye)
	{
		return _ht.Insert(valye);
	}

	iterator erase(iterator position)
	{
		return _ht.Erase(position);
	}
	////////////////////////////////////////////////////////////
	// bucket
	size_t bucket_count() { return _ht.BucketCount(); }
	size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
private:
	HT _ht;
};



	// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型
	// unordered_map在实现时，只需将hashbucket中的接口重新封装即可
	template<class K, class V, class HF = DefHashF<K>>
	class unordered_map
	{	
		struct KeyOfValue// 通过key获取value的操作
		{
			const K& operator()(const pair<K, V>& data)
			{
				return data.first;
			}
		};
		typedef HashBucket<K, pair<const K, V>, KeyOfValue, HF> HT;
		
		
	public:
		typename typedef HT::Iterator iterator;
	public:
		unordered_map() : _ht()
		{}
		////////////////////////////////////////////////////
		iterator begin() { return _ht.begin(); }
		iterator end() { return _ht.end(); }
		////////////////////////////////////////////////////////////
		// capacity
		size_t size()const { return _ht.size(); }
		bool empty()const { return _ht.empty(); }
		///////////////////////////////////////////////////////////
		// Acess
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));

			return ret.first->second;
		}
		const V& operator[](const K& key)const;
		//////////////////////////////////////////////////////////
		// lookup
		iterator find(const K& key) { return _ht.Find(key); }
		size_t count(const K& key) { return _ht.Count(key); }
		/////////////////////////////////////////////////
		// modify
		pair<iterator, bool> insert(const pair<K, V>& valye)
		{
			return _ht.Insert(valye);
		}

		iterator erase(iterator position)
		{
			return _ht.Erase(position);
		}
		////////////////////////////////////////////////////////////
		// bucket
		size_t bucket_count() { return _ht.BucketCount(); }
		size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
	private:
		HT _ht;
	};

	void test_map()
	{
		unordered_map<string, string> dict;
		dict.insert({ "sort", "排序" });
		dict.insert({ "left", "左边" });
		dict.insert({ "right", "右边" });
		dict["left"] = "左边，剩余";
		dict["insert"] = "插入";
		dict["string"];
		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			// 不能修改first，可以修改second
			//it->first += 'x';
				it->second += 'x';
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
	void test_set()
	{
		unordered_set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };
		for (auto e : a)
		{
			s.insert(e);
		}
		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
		unordered_set<int>::iterator it = s.begin();
		//*s.begin() = 5;
		while (it != s.end())
		{
			// 不⽀持修改
			*it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

int main() {
	unordered_map<int,int> k;
	k.insert(make_pair(50,50));
	int a2[] = { 19,30,5,36,13,20,21,12,24,96 };
	for (auto e : a2)
	{
		k.insert(make_pair(e,e));
	}
	for (auto e : k) {
		cout << e.second << endl;
	}
	test_map();
	test_set();
}